package com.leetcode.algorithm.y22.m08.w1;

import java.util.Arrays;

/**
 * 986. 区间列表的交集
 * 
 * https://leetcode.cn/problems/interval-list-intersections/
 * 
 * @author jie.deng
 *
 */
class Question0986Solution01 {

	public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
		int len1 = firstList.length;
		int len2 = secondList.length;
		if (len1 == 0 || len2 == 0) {
			return new int[][] {};
		}

		int[][] ret = new int[len1 + len2 - 1][2];

		int idx = 0;
		int idx1 = 0;
		int idx2 = 0;
		while (idx1 < len1 && idx2 < len2) {
			int[] arr1 = firstList[idx1];
			int[] arr2 = secondList[idx2];
			if (arr1[0] > arr2[1]) {
				idx2++;
			} else if (arr1[1] < arr2[0]) {
				idx1++;
			} else {
				int left = Math.max(arr1[0], arr2[0]);
				int right = Math.min(arr1[1], arr2[1]);
				ret[idx++] = new int[] { left, right };
				if (right == arr1[1]) {
					idx1++;
				}
				if (right == arr2[1]) {
					idx2++;
				}
			}
		}

		return Arrays.copyOfRange(ret, 0, idx);
	}

}